package com.xj.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 对称二叉树
 */
public class L101_判断二叉树是否对称 {

    /**
     *给定一个二叉树，检查它是否是镜像对称的。
     *
     * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
     *
     *     1
     *    / \
     *   2   2
     *  / \ / \
     * 3  4 4  3
     * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
     *
     *     1
     *    / \
     *   2   2
     *    \   \
     *    3    3
     *
     * 注意：
     * 如果同时满足下面的条件，两个树互为镜像：
     *      它们的两个根结点具有相同的值。
     *      每个树的右子树都与另一个树的左子树镜像对称。
     *
     */
    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(1);
        treeNode.left=new TreeNode(2);
        treeNode.left.left=new TreeNode(3);
        treeNode.left.right=new TreeNode(4);
        treeNode.right=new TreeNode(2);
        treeNode.right.left=new TreeNode(4);
        treeNode.right.right=new TreeNode(3);
        System.out.println(isSymmetricGood(treeNode));

        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.left.right=new TreeNode(3);
        root.right=new TreeNode(2);
        root.right.right=new TreeNode(3);
        System.out.println(isSymmetricGood(root));

        TreeNode root2=new TreeNode(1);
        root2.left=new TreeNode(2);
        root2.left.left=new TreeNode(2);
        root2.right=new TreeNode(2);
        root2.right.left=new TreeNode(2);
        System.out.println(isSymmetricGood(root2));
    }

    //官方解法：递归，两个相同的树比较
    public static boolean isSymmetricOffice(TreeNode root) {
        return isMirror(root, root);
    }

    public static boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
    }

    //精彩解法：使用递归，每次将两个互为镜像的节点放入队列，再取出来比较。
    //有一种宽度有限搜索的意思
    public static boolean isSymmetricGood(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            q.add(t1.left);
            q.add(t2.right);
            q.add(t1.right);
            q.add(t2.left);
        }
        return true;
    }

}
